/* tree.c--树的支持函数 */
#include <stdio.h>
#include <stdlib.h> 
#include <string.h>
#include "tree.h"

//局部数据类型
typedef struct pair	//内容包括一个两个树节点的指针
{
	Trnode* parent;
	Trnode* child;
 } Pair;			//在DeleteItem和SeekItem中使用
 
//局部函数的原型
static Trnode* MakeNode (const Item* pi);	//给新节点分配内存，输入一个只读节点的内容的指针
static bool ToLeft (const Item* i1, const Item* i2);	//定义并使用左节点
static bool ToRight (const Item* i1, const Item* i2);	//定义并使用右节点

static void AddNode (Trnode* new_node, Trnode* root);	//在树的底部添加新节点（不分配内存，不进行任何类型的赋值）
static void InOrder (const Trnode* root, void (*pfun) (Item item));	//给每个节点调用函数

static Pair SeekItem (const Item* pi, const Tree* ptree);	//返回一个包含两个指针的结构体Pair
static void DeleteNode (Trnode** ptr);
static void DeleteAllNodes (Trnode* ptr);//清空所有节点的内存（使用递归）

/*总结
1、函数分类
创建类型：AddItem、AddNode、MakeNode
删除类型：DeleteItem、DeleteNode、DeleteAll、DeleteAllNodes
查找：ToLeft、ToRight、InTree
遍历：Traverse、InOrder、SeekItem
2、函数间的引用关系
Toleft：被AddNode和SeekItem引用
MakeNode：被AddItem引用（基本就是AddItem的补全函数）
AddNode：被AddItem引用（基本就是AddItem的补全函数）
DeleteAllNodes：被DeleteAll引用（基本就是DeleteAll的补全函数）
DeleteNode：被DeleteItem引用（基本就是DeleteItem的补全函数）
InOrder：被Traverse引用（基本就是Traverse的补全函数）
*/

//函数定义(已补全)
void Initializetree (Tree* ptree) 		//把树的根节点指针初始化为空，把树的项数初始化为0 
{
	ptree->root = NULL;					//所以它只能用于初始化，而不能重置（重置需要DeleteAll()来释放内存才算清空了所有的项）
	ptree->size = 0;
}

//检测树是否为空 (已补全)
bool TreeIsEmpty (const Tree* ptree)
{
	if (ptree->root == NULL)
		return true;
	else
		return false;
	//return (ptree->root == NULL);不能这么写了，因为ptree这里是const类型数据
}

//检测树是否为满(已补全)
bool TreeIsFull (const Tree* ptree) 
{
	if (ptree->size == MAXITEMS)
		return true;
	else
		return false;
	//return (ptree->size = MAXITEMS);不能这么写了，因为ptree这里是const类型数据
}

//返回树的项数(已补全)
int TreeItemCount (const Tree* ptree)
{
	return ptree->size;
}

//给树添加新节点,然后填充输入的内容, 但并不会给左右指针赋值(已补全)
bool AddItem (const Item* pi, Tree* ptree)
{
	Trnode* new_node;
	 
	if (TreeIsFull(ptree))					//如果树是满的，返回错误提示
	{
		fprintf(stderr, "树是满的\n");
		return false;
	}

	if (SeekItem(pi, ptree).child != NULL)	//如果查找不到子节点
	{
		fprintf(stderr, "没有子节点的指针,应当新建一个项");
		return false;
	}
	//新建一个节点指针、分配内存并填充项的内容,但是并没有给左右指针赋值
	new_node = MakeNode(pi);

	//失败的情况:报错
	if (new_node == NULL)
	{
		fprintf (stderr, "不能创建新节点");
		return false;
	}
	//成功的情况:项数加1
	ptree->size++ ;	

	//给节点编辑访问路径
	if (ptree->root == NULL) 				//树为空,也就是我们在创建根节点
		ptree->root = new_node; 			//把新节点赋给根节点指针
	else
		Addnode(new_node, ptree->root);		//树不为空，在最底层创建新节点 
		
	return true;
}

//在树中确定一个项是否存在(已补全)
bool InTree (const Item* pi, const Tree* ptree)
{
	return (SeekItem(pi, ptree).child == NULL) ? false : true;	//三元选择符, 如果查找到的项没有子节点,说明已经到了树的底端仍然查找不到项,输出false.  如果查找到了, 输出true 
}

//在树中删除项的内容（已补全）
bool DeleteItem (const Item* pi, Tree* ptree) 
{
	Pair look;	//用于查找
	
	look = SeekItem (pi, ptree);	//查找一个节点，并把查找的节点赋值到子节点中，把查找的节点的上层节点赋值到父节点中
	if (look.child = NULL)			//没有子节点，也就是树中找不到查找的节点，则返回错误值
		return false;
	
	if (look.parent = NULL)			//如果没有父节点(查找的项就是根)
		DeleteNode (&ptree->root);	//删除树的根节点
	else if (look.parent->left == look.child)	//如果父元素的左指针是子元素(找到了)
		DeleteNode (&look.parent->left);		//删除子元素
	else										//其它情况(父元素的右指针是子元素)（也是找到了）
		DeleteNode (&look.parent->right);		//删除子元素
	ptree->size--;	//项数减1 
	
	return true;
}

//对树中的项遍历函数（已补全）
void Traverse (const Tree* ptree, void (*pfun)(Item item))
{
	if (ptree != NULL)			//如果树不为空
		InOrder(ptree->root, pfun);//调用InOreder函数对所有的节点递归调用函数
}

//清空树内存（已补全）
void DeleteAll (Tree* ptree)
{
	if (ptree != NULL)		//如果树不为空，对其调用DeleteAllNodes()函数，使用递归的方法清空所有节点。然后把ptree的各项设置清零
		DeleteAllNodes (ptree->root);
	ptree->root = NULL;
	ptree->size = 0;
}

/*局部函数*/

//使用递归的方法对树的每个节点调用任意函数（已补全）
static void InOrder (const Trnode* root, void (*pfun)(Item item))
{
	if (root != NULL)	//如果输入的节点不为空
	{
		InOrder (root->left, pfun);	//对当前项的左指针调用自身,再对当前项的左指针项再调用自身……层层嵌套
		(*pfun)(root->item);		//等到嵌套的节点为空时, 给倒数第二层节点调用输入的函数
		InOrder (root->right, pfun);//调用完毕后,给倒数第二层节点的右指针调用函数,然后开始解套,给倒数第三层的左指针调用函数……总之这个方法可以遍历所有的节点
		//这里就显示出递归的优势了。如果是循环，嵌套的层数本身都是一个变量，直接就抓瞎了。
	}
}


//使用递归的方法清空所有节点的内存（已补全）
static void DeleteAllNodes (Trnode* root)
{
	Trnode * pright;		//建立缓存(因为是链表,一会删除了子节点后, 怕找不回原来的节点没办法推进,所以先缓存一下原来的节点)
	
	if (root != NULL)		//如果输入的节点不为空
	{
		pright = root->right;			//给当前节点的右指针建立缓存
		DeleteAllNodes (root->left);	//对当前节点的左指针递归调用自身,层层嵌套,调用后层层解套(有多少个套,在嵌套的过程中就建立了多少个局部作用域的缓存，其它的本质和上面一样)
		free(root);
		DeleteAllNodes(pright);			//嵌套到底后,开始给倒数第二层的右指针也调用函数,然后又给右指针的左指针调用函数,从左到右遍历一遍
	}
}

//在树的底部添加一个新节点并编辑访问路径（已补全）
static void AddNode (Trnode* new_node, Trnode* root)	//实参分别是新节点和新节点前的子节点
{
	if (ToLeft ( &(new_node->item), &(root->item)))		//判断左指针的符合条件
	{
		if (root->left == NULL)			//如果输入的节点的左指针是空的，就在左指针上创建新节点。
			root->left = new_node;
		else							//如果不是，递归调用自身，不断进行判断。过程中如果出现上述的满足条件的情况就停止。如果到了底部还没有匹配的，就调用内层else的命令在底层节点的左指针上创建一个新节点，然后自导自演地触发上述条件。
			AddNode (new_node, root->left);
	}

	else if (ToRight (&new_node->item, &root->item))	//或者新节点的项的内容和输入的节点的项的内容
	{
		if (root->right == NULL)
			root->right = new_node;
		else
			AddNode (new_node, root->right);
	}
	else			//如果左右指针都歇菜了，说明有问题了。
	{
		fprintf(stderr, "在AddNode()中发生错误\n");
		exit(1);
	}
}

//左右指针的定义和递归查找判断函数（已补全）

/*这个有必要好好说明一下
首先，这个函数并不是仅仅为了查找用的，我们发现在创建新节点和填充项的内容时也用到了它。有递归的地方就有它。所以它的功能其实更广：它可以定义左指针
在函数体里可以看到，只要是strcmp返回的值<=0，就会返回true。在程序里，它的意思其实是：strcmp返回的值<0的会被分配到左指针去
这样当然可能导致左右指针数量不均，不过对于二叉树来讲无所谓。
右指针的判断条件是strcmp返回的值>=0，那么如果字符串刚好匹配返回0的时候，两个函数都会返回true，这时需要在程序中进行一些操作来避免继续进行查找或递归*/
static bool ToLeft (const Item* i1, const Item* i2)
{
	int comp1;		//用来比较的逻辑值,局部变量而已
	
	if ( (comp1 = strcmp (i1->petname, i2->petname) ) < 0)
		return true;
	else if (comp1 == 0 && strcmp (i1->petkind, i2->petkind) < 0 )
		return true;
	else					//如果>0，返回false，交给右指针函数
		return false;
}
static bool ToRight (const Item* i1, const Item* i2)
{
	int comp1;

	if ( (comp1 = strcmp(i1->petname, i2->petname)) > 0)
		return true;
	else if( comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
		return true;
	else
		return false;
}

//新建一个节点的指针并分配内存和给项的内容赋值, 但是并不给指针内容赋值（已补全）
static Trnode* MakeNode (const Item* pi)		
{
	Trnode* new_node;
	
	new_node = (Trnode*)malloc(sizeof(Trnode));
	if (new_node != NULL)			//如果成功给新节点分配了内存空间, 则填充项的内容,然后初始化左右指针为空,返回新节点.
	{
		new_node->item = *pi;		//把新节点的
		new_node->left = NULL;
		new_node->right = NULL;
	}
	return new_node;			//返回新节点的指针
}


//查找一个节点（已补全）
static Pair SeekItem (const Item* pi, const Tree* ptree)
{
	Pair look;				//用于查找的项
	look.parent = NULL;		//指向父元素的节点指针初始化为空
	look.child = ptree->root;//指向子元素节点指针赋值为根节点
	
	if (look.child == NULL)	//如果指向的子元素节点为空,说明树还没有赋值,这时直接把根节点返回.
		return look;
	
	while (look.child != NULL)	//如果寻找的当前节点的子节点指针不为空,也就是还没有到树的底端,就一直重复循环,也就是对树的遍历
	{
		if (ToLeft (pi, &(look.child->item)) )	//如果要找的节点的项的内容在左指针中，把当前节点存储到父节点上，子节点接着赋值为左节点，然后再次比较。实现树的比较查找。（因为整个树都是用ASCII码的大小来编排左右节点的，所以顺序非常统一，前面的节点的ASCII码一定大于/小于后面的。这样我们就可以实现隔着节点就可以比较整个树）
		{
			look.parent = look.child;
			look.child = (look.child->left);
		}
		else if (ToRight (pi, &look.child->item) )
		{
			look.parent = look.child;
			look.child = look.child->right;
		}
		else
			break;
	}
	
	return look;		//最后找到，然后返回Pair类型数据look，也就是子节点为查找的节点，父节点为查找的节点的上层节点
}

//在树中查找和删除一个节点，并拼接它的子节点。（已补全）
static void DeleteNode (Trnode** ptr)
{
	Trnode* temp;	//建立局部指针
	
	if ( (*ptr)->left == NULL)	//如果输入的树的节点的左指针为空（左底层）
	{
		temp = *ptr;			//给局部指针赋值
		*ptr = (*ptr)->right;	//把原节点改为原节点的右指针节点
		free(temp);				//删除局部指针（相当于删除了原节点的指针）
	}
	else if ( (*ptr)->right == NULL)//如果输入的树的节点的右指针为空（右底层）
	{
		temp = *ptr;
		*ptr = (*ptr)->left;
		free(temp);
	}
	else			//其它情况（非底层），这个时候要把节点的子指针进行一个接合
	{
		for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)	//初始把原节点的左指针赋给局部指针，然后把局部指针不断地指向原节点左指针的各级右指针，直到右指针为空（到达原节点左指针的右底层）
			continue;
		temp->right = (*ptr)->right;	//把右底层的右指针（空）指向原节点的右指针
		temp = *ptr;					//把局部指针指向原节点
		*ptr = (*ptr)->left;			//把原节点指向原节点的左指针
		free(temp);						//删除局部指针（删除原节点）
		//最后，（原节点的上层节点）的（指向原节点的指针）被修改为指向（原节点的左指针）；
		//（原节点的左指针的右底层）被修改为指向（原节点的右节点），相当于把（原节点右指针的二叉树）嫁接到了（原节点左指针的右底层）上。这无所谓，反正这个二叉树被我们设置为全局查找。只要原节点的树的地址没丢就行。
		//（原节点的左指针）原来的树没有变，只是右底层被嫁接了。（原节点的上层节点）原来指向原节点的树变成了指向原节点的左指针，原节点左指针包含了原节点右指针，一个节点也没有丢。
	 }
}